package LeetCode75;

/**
 * 643. 子数组最大平均数 I
 * 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
 *
 * 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
 *
 * 任何误差小于 10-5 的答案都将被视为正确答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,12,-5,-6,50,3], k = 4
 * 输出：12.75
 * 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
 * 示例 2：
 *
 * 输入：nums = [5], k = 1
 * 输出：5.00000
 */
public class T0643_子数组最大平均数1 {
    //因为子数组 长度确定 其实就是求子数组最大和 ,最后返回 最大和/K 即可
    public static double findMaxAverage(int[] nums, int k) {
        //计算数组的前缀和
        int[] ints = new int[nums.length + 1];
        int sum = 0;
        ints[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = nums[i] + sum;
            ints[i + 1] = sum;
        }

        //遍历前缀和数组 从k 开始遍历(坐标K的值 是从1到k 的和 )  那n到(n-k)的和 就是 ints(n)-ints(n-k)
        int max = Integer.MIN_VALUE;

        for (int i = k; i < ints.length; i++) {
            //这里为了方便 计算边界条件 将前缀和数组的长度加1 第一个数设置为0
            max = Math.max(max, ints[i] - ints[i - k]);
        }

        //转为double 再计算平均数
        return (double) max / k;
    }

    public static void main(String[] args) {
        double maxAverage = findMaxAverage(new int[]{1, 12, -5, -6, 50, 3}, 4);
    }
}
